package review;

import java.util.Arrays;
import java.util.Random;

public class 快速排序 {

    /**
     * 选base = left，定义左右指针，low，high
     */
    public static void quickSort(int[] array,int left,int right) {
        // 因为是递归，所以必须加递归结束条件，否则出现死循环，数组越界
        if(array == null || array.length < 1 || left >= right) {
            return;
        }
        int low = left;
        int high = right;
        int base = array[left];
        while (low != high) {
            // high从右边向左边检索，找到了比base小的停下来，
            while (low < high && array[high] >= base) {
                high--;
            }
            // low从左向右检索，找到了比base大的停下来，
            while (low < high && array[low] <= base) {
                low++;
            }
            // 位置交换，继续检索，
            int temp = array[low];
            array[low] = array[high];
            array[high] = temp;
        }
        // 直到low = high，交换low和base的位置
        array[left] = array[low];
        array[low] = base;
        // 之后递归，先检索左边区间的，在加索右边区间的，按照上面步骤(先从右边high指针检索，在从左边检索)
        quickSort(array,left,low - 1);

        quickSort(array,low + 1,right);
    }

    public static void sort(int[] array,int left,int right){
        if(array == null || array.length <= 0 || left >= right) {
            return;
        }
        int base = array[left];
        int low = left;
        int high = right;
        while (low != high) {
            // 先从右边向左边检索
            while (low < high && array[high] >= base) {
                high--;
            }
            // 在从左边向右边检索
            while (low < high && array[low] <= base) {
                low++;
            }

            int temp = array[low];
            array[low] = array[high];
            array[high] = temp;
        }
        array[left] = array[low];
        array[low] = base;
        // 先检索左边的区间，再检索右边的区间
        sort(array,left,low - 1);
        sort(array,low + 1,right);
    }

    public static void main(String[] args) {
        int[] array = new int[30];
        Random random = new Random();
        for (int i = 0; i < array.length; i++) {
            array[i] = random.nextInt(50);
        }
        quickSort(array, 0, array.length - 1);
        System.out.println("快速排序之后的数据:" + Arrays.toString(array));
    }
}
